/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Lenovo
 * Date: 2025-04-27
 * Time: 21:52
 */
public class PartitionLinkedListTest {

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    static class Solution {
        private ListNode head;

        public Solution(ListNode head) {
            this.head = head;
        }

        public ListNode partition(int x) {
            // 当前节点，从头节点开始遍历整个链表
            ListNode current = head;

            // 小值链表的头节点和尾节点（存储所有值小于x的节点）
            ListNode smallHead = null;
            ListNode smallTail = null;
            // 大值链表的头节点和尾节点（存储所有值大于等于x的节点）
            ListNode largeHead = null;
            ListNode largeTail = null;

            // 遍历原链表，将节点按值分配到小链表或大链表
            while (current != null) {
                if (current.val < x) {
                    // 当前节点值小于x，加入小链表
                    if (smallHead == null) {
                        // 小链表为空时，头尾均指向当前节点（首次插入）
                        smallHead = smallTail = current;
                    } else {
                        // 小链表不为空，将当前节点追加到尾节点后，并更新尾节点
                        smallTail.next = current;
                        smallTail = smallTail.next;
                    }
                } else {
                    // 当前节点值大于等于x，加入大链表
                    if (largeHead == null) {
                        // 大链表为空时，头尾均指向当前节点（首次插入）
                        largeHead = largeTail = current;
                    } else {
                        // 大链表不为空，将当前节点追加到尾节点后，并更新尾节点
                        largeTail.next = current;
                        largeTail = largeTail.next;
                    }
                }
                // 移动到原链表的下一个节点
                current = current.next;
            }


            //以下是合并链表

            // 若小链表为空的情况（所有节点均在大链表中）
            if (smallHead == null) {
                return largeHead;  // 直接返回大链表的头节点
            }

            // 否则连接小链表和大链表
            smallTail.next = largeHead;  // 小链表的尾部指向大链表的头部

            // 关键细节：若大链表非空，需确保其尾节点的next为null，防止链表成环
            if (largeHead != null) {
                largeTail.next = null;
            }

            // 返回合并后的链表头节点（小链表的头节点）
            return smallHead;
        }
    }

    public static void main(String[] args) {
        test1();
        test2();
        test3();
        test4();
        test5();
    }

    private static void test1() {
        // 测试用例1：普通情况，x=3
        ListNode head = createLinkedList(new int[]{1, 4, 3, 2, 5, 2});
        Solution solution = new Solution(head);
        ListNode result = solution.partition(3);
        System.out.print("Test Case 1: ");
        printList(result); //  1 -> 2 -> 2 -> 4 -> 3 -> 5
    }

    private static void test2() {
        // 测试用例2：所有节点都小于x，x=5
        ListNode head = createLinkedList(new int[]{1, 2, 3, 4});
        Solution solution = new Solution(head);
        ListNode result = solution.partition(5);
        System.out.print("Test Case 2: ");
        printList(result); // 原顺序 1 -> 2 -> 3 -> 4
    }

    private static void test3() {
        // 测试用例3：所有节点都大于等于x，x=2
        ListNode head = createLinkedList(new int[]{3, 4, 5});
        Solution solution = new Solution(head);
        ListNode result = solution.partition(2);
        System.out.print("Test Case 3: ");
        printList(result); // 原顺序 3 -> 4 -> 5
    }

    private static void test4() {
        // 测试用例4：混合情况，x=0
        ListNode head = createLinkedList(new int[]{2, 1, 3});
        Solution solution = new Solution(head);
        ListNode result = solution.partition(0);
        System.out.print("Test Case 4: ");
        printList(result); //  原顺序（所有节点 >=0） 2 -> 1 -> 3
    }

    private static void test5() {
        // 测试用例5：空链表
        ListNode head = createLinkedList(new int[]{});
        Solution solution = new Solution(head);
        ListNode result = solution.partition(3);
        System.out.print("Test Case 5: ");
        printList(result); // 预期: 空链表
    }

    // 工具方法：将数组转换为链表
    private static ListNode createLinkedList(int[] arr) {
        // 边界检查：若数组为空或长度为0，直接返回空链表
        if (arr == null || arr.length == 0) return null;

        // 创建一个虚拟头节点（dummy node），值为-1（值不影响结果）
        // 作用：简化链表头节点的处理逻辑，避免单独处理头节点的特殊情况
        ListNode dummy = new ListNode(-1);

        // 定义一个指针 current，初始指向 dummy 节点
        // current 的作用是追踪当前链表的末尾位置，方便逐个添加新节点
        ListNode current = dummy;

        // 遍历数组中的每个元素
        for (int num : arr) {
            // 创建新节点，值为当前数组元素 num
            ListNode newNode = new ListNode(num);

            // 将新节点添加到链表的末尾：
            // 当前指针的 next 指向新节点（即把新节点连接到链表尾部）
            current.next = newNode;

            // 移动 current 指针到新节点，保持 current 始终指向链表末尾
            current = current.next;

            // 示例：假设数组为 [1,2,3]
            // 第一次循环：dummy -> 1 (current 指向1)
            // 第二次循环：dummy -> 1 -> 2 (current 指向2)
            // 第三次循环：dummy -> 1 -> 2 -> 3 (current 指向3)
        }

        // 最终返回 dummy 的下一个节点（即真正的链表头节点）
        // 因为 dummy 本身是辅助节点，不是链表的一部分
        return dummy.next;
    }
    // 打印链表
    private static void printList(ListNode head) {
        if (head == null) {
            System.out.println("空链表");
            return;
        }
        ListNode current = head;
        while (current != null) {
            System.out.print(current.val);
            if (current.next != null) {
                System.out.print(" -> ");
            }
            current = current.next;
        }
        System.out.println();
    }
}
